/**
 * 双指针
 * 19.删除链表的倒数第N个节点
 */
public class Exerciser1 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 双指针 - 快慢指针
        // 添加一个哨兵位的节点，可以防止处理删除head节点的情况
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode fast = head;
        ListNode slow = newHead;
        // 1.fast先走，让fast和slow 之间保持n这个节点数
        for(int i = 0;i < n;i++) {
            fast = fast.next;
        }
        // 2.这个时候fast和slow中间就存在n个节点，之后一起往后走，直至 fast为null，这时slow 就是要删除节点的前一个节点
        while(fast != null) {
            fast =fast.next;
            slow = slow.next;
        }

        // 3.删除节点
        slow.next = slow.next.next;
        return newHead.next;
    }
}
